package com.lishem.top100._07linkedlist;

import com.lishem.common.ListNode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/palindrome-linked-list/description/
 * <p>
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表
 * <p>
 * 如果是，返回 true ；否则，返回 false 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,2,2,1]
 * <p>
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [1,2]
 * <p>
 * 输出：false
 */
public class _03LetCode234_回文链表 {

    /**
     * 不使用额外空间的解法
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!= null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode pre = null;
        ListNode next = null;
        ListNode cur = slow;
        while (cur != null){
            next= cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 反转完了，开始比较
        boolean res = true;
        cur = pre;
        fast = head;
        while (fast!=slow){
            if (fast.val != cur.val){
                res = false;
                break;
            }
            cur = cur.next;
            fast = fast.next;
        }
        // 反转回来
        pre = null;
        cur = pre;
        while (cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return res;
    }

    /**
     * 节约一半空间
     */
    public boolean isPalindrome2(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            stack.push(slow);
            fast = fast.next.next;
            slow = slow.next;
        }
        // 通过 fast 的状态判断总数
        if (fast != null){
            slow = slow.next;
        }
        while (slow!= null){
            if (stack.pop().val!= slow.val){
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    /**
     * 时间复杂度 O(n)解法
     */
    public boolean isPalindrome1(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur= head;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()){
            if (stack.pop().val != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public static void main(String[] args) {
        _03LetCode234_回文链表 sol = new _03LetCode234_回文链表();

        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(2);
        head1.next.next.next = new ListNode(1);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        System.out.println(sol.isPalindrome1(head1));
        System.out.println(sol.isPalindrome1(head2));

        System.out.println("--------------------------");
        System.out.println(sol.isPalindrome2(head1));
        System.out.println(sol.isPalindrome2(head2));

        System.out.println("--------------------------");
        System.out.println(sol.isPalindrome(head1));
        System.out.println(sol.isPalindrome(head2));
    }
}
